package com.jun.leetcode.difficult.controller;

import io.swagger.annotations.Api;
import io.swagger.annotations.ApiOperation;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;


/**
 * @author : gelianbin
 * @createDate : 7/23/2021
 */
@RestController
@RequestMapping("/difficult")
@Api(tags = "AC困难控制器")
public class DiffController {

    @GetMapping("/isMatch")
    @ApiOperation(value = "正则表达式匹配", notes = "给你一个字符串s和一个字符规律p，请你来实现一个支持" +
            " '.'和'*'的正则表达式匹配。" +
            "'.' 匹配任意单个字符" +
            "'*' 匹配零个或多个前面的那一个元素" +
            "所谓匹配，是要涵盖整个字符串s的，而不是部分字符串")
    public boolean isMatch(String s, String p) {
        if (p==null){
            if (s==null){
                return true;
            }else{
                return false;
            }
        }

        if (s==null && p.length()==1){
            return false;
        }

        int m = s.length()+1;
        int n = p.length()+1;

        boolean[][]dp = new boolean[m][n];

        dp[0][0] = true;

        for (int j=2;j<n;j++){
            if (p.charAt(j-1)=='*'){
                dp[0][j] = dp[0][j-2];
            }
        }

        for (int r=1;r<m;r++){
            int i = r-1;
            for (int c=1;c<n;c++){
                int j = c-1;
                if (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.'){
                    dp[r][c] = dp[r-1][c-1];
                }else if (p.charAt(j)=='*'){
                    if (p.charAt(j-1)==s.charAt(i) || p.charAt(j-1)=='.'){
                        dp[r][c] = dp[r-1][c] || dp[r][c-2];
                    }else{
                        dp[r][c] = dp[r][c-2];
                    }
                }else{
                    dp[r][c] = false;
                }

            }
        }
        return dp[m-1][n-1];
    }
}
